1. Field of the Invention
The present invention relates to the field of memory caches. More specifically, the present invention relates to a method for updating an Cache LRU tree.
2. Description of Background
Cache memories, in which a Central Processing Unit (CPU) stores its most recently used data, are a fixture in modern computer designs. Since not all data currently in use by the CPU can fit within a cache's limited storage capacity, an algorithm must be established to decide which pieces of data are to be displaced when new data arrives in the cache. The most common cache management algorithm is the Least Recently Used (LRU) algorithm. In the LRU approach, the data that has been in the cache for the longest period of time without being used by the CPU are favored for replacement when space is needed in the cache memory.
One shortcoming of the LRU algorithm is that it focuses on a single characteristic of the data stored in the cache memory, namely, the relative length of time lines have remained unreferenced in the set. What is needed is an algorithm that can factor in a generic priority associated with a line. The initial priority of a line is determined external to the cache and is provided to the cache when the line enters the cache